package main

// 零钱兑换：凑成总金额所需的最少硬币个数

func coinChange(coins []int, amount int) int {

	// dp[i]: 组成i的最小金币数量
	// dp[0]-dp[i-1]已知
	// dp[i] = min{f(i-c_j)}+1  c_j：第j枚金币面值

	if amount < 1 && len(coins) < 1 {
		return -1
	}
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1 // 极大值
	}
	dp[0] = 0

	for i := 1; i <= amount; i++ {
		for j := 0; j < len(coins); j++ {
			if coins[j] <= i { // 否则i-c_j为负数
				dp[i] = min(dp[i], dp[i-coins[j]]+1)
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}

	return dp[amount]
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func main() {

}
